package jianzhi_offer;

/**
 * @author: zhouyang
 * @descrpition:
 * @time: 2019-04-17 09:59
 */
public class _64_矩阵中的路径 {
    public static void main(String[] args) {
        _64_矩阵中的路径 test = new _64_矩阵中的路径();
        Object obj =test.hasPath("ABCESFCSADEE".toCharArray(),3,4,"ABCCED".toCharArray());
    }

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        if(str.length == 0) return true;
        boolean visited[] = new boolean[matrix.length];
        for(int i=0;i<matrix.length;++i){
            if(matrix[i] == str[0]){
                visited[i] = true;
                if(dfs(matrix,rows,cols,str,0,visited,i)) return true;
                visited[i] = false;
            }
        }
        return false;
    }

    public boolean dfs(char[] matrix,int rows,int cols,char []str,int index,boolean[] visited,int now){
        if(index == str.length-1) return true;
        int r = now/cols;
        int c = now%cols;
        if(c > 0 && !visited[now-1] && matrix[now-1] == str[index+1]){//左
            visited[now-1] = true;
            if (dfs(matrix,rows,cols,str,index+1,visited,now-1))
                return true;
            visited[now-1] = false;
        }
        if(c != cols-1 && !visited[now+1] && matrix[now+1] == str[index+1]){//右
            visited[now+1] = true;
            if (dfs(matrix,rows,cols,str,index+1,visited,now+1))
                return true;
            visited[now+1] = false;
        }
        if(r > 0 && !visited[now-cols] && matrix[now-cols] == str[index+1]){//上
            visited[now-cols] = true;
            if (dfs(matrix,rows,cols,str,index+1,visited,now-cols))
                return true;
            visited[now-cols] = false;
        }
        if(r != rows-1 && !visited[now+cols] && matrix[now+cols] == str[index+1]){//左
            visited[now+cols] = true;
            if (dfs(matrix,rows,cols,str,index+1,visited,now+cols))
                return true;
            visited[now+cols] = false;
        }
        return false;
    }
}
